/**
 * 第三版并查集，额外增加一个数组，用来记录相连节点元素个数
 */
public class UnionFind3 implements UF{

    private int[] parent;

    private int[] sz;           // sz[i]表示以i为根的集合中元素的个数

    public UnionFind3(int size) {
        parent = new int[size];
        sz = new int[size];

        for (int i = 0; i < size; i++) {
            parent [i] = i;
            sz[i] = 1;
        }
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    /**
     * 查找元素的根节点。
     *
     * 该函数用于在并查集中查找指定元素的根节点。并查集是一种数据结构，用于高效地处理集合的合并和查询操作。
     * 在这个过程中，它使用路径压缩技术来优化性能，即直接将查找过程中经过的节点指向最终的根节点，以减少后续查找的次数。
     * O(h)复杂度，h为树的高度
     * @param p 要查找根节点的元素。
     * @return 元素p的根节点。
     */
    private int find(int p){

        if (p < 0 && p >= parent.length){
            throw new IllegalArgumentException("p is out of bound. ");
        }
        // 当p不是自己的父节点时，继续向上查找
        while (p != parent[p]){
            p = parent[p];
        }
        // 返回找到的根节点
        return p;
    }


    /**
     * 检查两个元素是否属于同一个集合。
     *
     * 此方法用于判断在并查集数据结构中，两个给定的元素p和q是否属于同一个集合。它通过比较两者在并查集中的根节点是否相同来实现。
     * 如果p和q的根节点相同，则说明它们属于同一个集合，方法返回true；否则，返回false。
     *O(h)复杂度
     * @param p 第一个元素的索引
     * @param q 第二个元素的索引
     * @return 如果p和q属于同一个集合，则返回true；否则返回false。
     */
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }


    /**
     * 将两个元素所属的集合合并。
     *
     * 此方法的目的是通过调整父节点的指向，将两个不同的集合合并成一个。它首先找到元素p和q的根节点，
     * 如果p和q的根节点相同，说明它们已经属于同一个集合，无需进行合并操作。如果根节点不同，
     * 则将p的根节点的父节点设置为q的根节点，以此来合并两个集合。
     *
     * @param p 第一个元素的索引
     * @param q 第二个元素的索引
     */
    @Override
    public void unionElements(int p, int q) {
        // 查找元素p的根节点
        int pRoot = find(p);
        // 查找元素q的根节点
        int qRoot = find(q);

        // 如果p和q的根节点相同，说明它们已经属于同一个集合，无需合并
        if (pRoot == qRoot){
            return;
        }
        // 根据两个元素所在树的元素个数不同判断合并方向
        // 将元素个数少的集合合并到元素个数多的集合上
        if (sz[pRoot] < sz[qRoot]) {
            // 将p的根节点的父节点设置为q的根节点，合并两个集合
            parent[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        }else {
            parent[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];
        }
    }

}
